package com.fanshuai2.niuke.search.dfs;
import java.util.*;

/**
 * 若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的 N （ N 为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。
 *
 * 输入:
 * 有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。
 *
 * 输出:
 * 输出一个整数 K ，表示你求得的“最佳方案”组成“素数伴侣”的对数。
 *
 * 首先定义两个list容器，分别存储输入整数中的奇数和偶数。
 * 然后利用匈牙利算法找到“素数伴侣”对数最多时的配对数。匈牙利算法的核心思想是先到先得，能让就让。
 * 最后输出“素数伴侣”最多时的对数。
 */
public class PrimeParts {
    static int maxParts(int[] a) {
        List<Integer> odds = new ArrayList<>();
        List<Integer> evens = new ArrayList<>();
        for (int i = 0; i < a.length; i++) {
            if (a[i] % 2 == 0) {
                evens.add(a[i]);
            } else {
                odds.add(a[i]);
            }
        }

        int[] matchEvens = new int[evens.size()];
        int count = 0;
        for (int i = 0; i < odds.size(); i++) {
            int odd = odds.get(i);
            boolean[] visited = new boolean[evens.size()];
            if (find(odd, evens, visited, matchEvens)) {
                count++;
            }
        }
        return count;
    }

    static boolean find(int odd, List<Integer> evens, boolean[] visited,
                        int[] matchEvens) {
        for (int i = 0; i < evens.size(); i++) {
            if (!visited[i] && isPrime(odd + evens.get(i))) {
                visited[i] = true;

                if (matchEvens[i] == 0 ||
                        find(matchEvens[i], evens, visited, matchEvens)) {
                    matchEvens[i] = odd;
                    return true;
                }
            }
        }
        return false;
    }

    static boolean isPrime(int x) {
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] a = new int[n];

            for (int i = 0; i < a.length; i++) {
                a[i] = in.nextInt();
            }
            System.out.println(maxParts(a));

        }
    }
}
